home *** CD-ROM | disk | FTP | other *** search
/ Ian & Stuart's Australian Mac: Not for Sale / Another.not.for.sale (Australia).iso / hold me in your arms / PGP 2.6 / rsaref Toolkit / source / nn.c < prev    next >
C/C++ Source or Header  |  1994-05-22  |  14KB  |  659 lines
  1. /* NN.C - natural numbers routines
  2.  */
  3.  
  4. /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
  5.    Security, Inc. All rights reserved.
  6.  */
  7.  
  8. /*
  9.  * CHANGES MADE TO THIS FILE UNDER RSAREF license clause 1(c):
  10.  *
  11.  * For the MIT PGP 2.6 distribution, this file was modified to permit
  12.  * replacement of the NN_ModExp routine by an equivalent routine
  13.  * contained in the PGP 2.6 sources.  To enable this change, an #ifdef
  14.  * was added to this file (search for #ifndef USEMPILIB
  15.  * below).  RSAREF *must* be compiled with USEMPILIB defined for this
  16.  * change to occur.
  17.  *
  18.  * Change made May 21, 1994.
  19.  */
  20.  
  21. #include "global.h"
  22. #include "rsaref.h"
  23. #include "nn.h"
  24. #include "digit.h"
  25.  
  26. static NN_DIGIT NN_LShift PROTO_LIST 
  27.   ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
  28. static NN_DIGIT NN_RShift PROTO_LIST
  29.   ((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
  30. static void NN_Div PROTO_LIST
  31.   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *,
  32.     unsigned int));
  33.  
  34. static NN_DIGIT NN_AddDigitMult PROTO_LIST 
  35.   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  36. static NN_DIGIT NN_SubDigitMult PROTO_LIST 
  37.   ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));
  38.  
  39. static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));
  40.  
  41. /* Decodes character string b into a, where character string is ordered
  42.    from most to least significant.
  43.  
  44.    Length: a[digits], b[len].
  45.    Assumes b[i] = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
  46.    significant bytes are truncated.)
  47.  */
  48. void NN_Decode (a, digits, b, len)
  49. NN_DIGIT *a;
  50. unsigned char *b;
  51. unsigned int digits, len;
  52. {
  53.   NN_DIGIT t;
  54.   int j;
  55.   unsigned int i, u;
  56.   
  57.   for (i = 0, j = len - 1; j >= 0; i++) {
  58.     t = 0;
  59.     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  60.       t |= ((NN_DIGIT)b[j]) << u;
  61.     a[i] = t;
  62.   }
  63.   
  64.   for (; i < digits; i++)
  65.     a[i] = 0;
  66. }
  67.  
  68. /* Encodes b into character string a, where character string is ordered
  69.    from most to least significant.
  70.  
  71.    Lengths: a[len], b[digits].
  72.    Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
  73.    digits are truncated.)
  74.  */
  75. void NN_Encode (a, len, b, digits)
  76. NN_DIGIT *b;
  77. unsigned char *a;
  78. unsigned int digits, len;
  79. {
  80.   NN_DIGIT t;
  81.   int j;
  82.   unsigned int i, u;
  83.  
  84.   for (i = 0, j = len - 1; i < digits; i++) {
  85.     t = b[i];
  86.     for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
  87.       a[j] = (unsigned char)(t >> u);
  88.   }
  89.  
  90.   for (; j >= 0; j--)
  91.     a[j] = 0;
  92. }
  93.  
  94. /* Assigns a = 0.
  95.  
  96.    Lengths: a[digits], b[digits].
  97.  */
  98. void NN_Assign (a, b, digits)
  99. NN_DIGIT *a, *b;
  100. unsigned int digits;
  101. {
  102.   unsigned int i;
  103.  
  104.   for (i = 0; i < digits; i++)
  105.     a[i] = b[i];
  106. }
  107.  
  108. /* Assigns a = 0.
  109.  
  110.    Lengths: a[digits].
  111.  */
  112. void NN_AssignZero (a, digits)
  113. NN_DIGIT *a;
  114. unsigned int digits;
  115. {
  116.   unsigned int i;
  117.  
  118.   for (i = 0; i < digits; i++)
  119.     a[i] = 0;
  120. }
  121.  
  122. /* Assigns a = 2^b.
  123.  
  124.    Lengths: a[digits].
  125.    Requires b < digits * NN_DIGIT_BITS.
  126.  */
  127. void NN_Assign2Exp (a, b, digits)
  128. NN_DIGIT *a;
  129. unsigned int b, digits;
  130. {
  131.   NN_AssignZero (a, digits);
  132.  
  133.   if (b >= digits * NN_DIGIT_BITS)
  134.     return;
  135.  
  136.   a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
  137. }
  138.  
  139. /* Computes a = b + c. Returns carry.
  140.  
  141.    Lengths: a[digits], b[digits], c[digits].
  142.  */
  143. NN_DIGIT NN_Add (a, b, c, digits)
  144. NN_DIGIT *a, *b, *c;
  145. unsigned int digits;
  146. {
  147.   NN_DIGIT ai, carry;
  148.   unsigned int i;
  149.  
  150.   carry = 0;
  151.  
  152.   for (i = 0; i < digits; i++) {
  153.     if ((ai = b[i] + carry) < carry)
  154.       ai = c[i];
  155.     else if ((ai += c[i]) < c[i])
  156.       carry = 1;
  157.     else
  158.       carry = 0;
  159.     a[i] = ai;
  160.   }
  161.  
  162.   return (carry);
  163. }
  164.  
  165. /* Computes a = b - c. Returns borrow.
  166.  
  167.    Lengths: a[digits], b[digits], c[digits].
  168.  */
  169. NN_DIGIT NN_Sub (a, b, c, digits)
  170. NN_DIGIT *a, *b, *c;
  171. unsigned int digits;
  172. {
  173.   NN_DIGIT ai, borrow;
  174.   unsigned int i;
  175.  
  176.   borrow = 0;
  177.  
  178.   for (i = 0; i < digits; i++) {
  179.     if ((ai = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
  180.       ai = MAX_NN_DIGIT - c[i];
  181.     else if ((ai -= c[i]) > (MAX_NN_DIGIT - c[i]))
  182.       borrow = 1;
  183.     else
  184.       borrow = 0;
  185.     a[i] = ai;
  186.   }
  187.  
  188.   return (borrow);
  189. }
  190.  
  191. /* Computes a = b * c.
  192.  
  193.    Lengths: a[2*digits], b[digits], c[digits].
  194.    Assumes digits < MAX_NN_DIGITS.
  195.  */
  196. void NN_Mult (a, b, c, digits)
  197. NN_DIGIT *a, *b, *c;
  198. unsigned int digits;
  199. {
  200.   NN_DIGIT t[2*MAX_NN_DIGITS];
  201.   unsigned int bDigits, cDigits, i;
  202.  
  203.   NN_AssignZero (t, 2 * digits);
  204.   
  205.   bDigits = NN_Digits (b, digits);
  206.   cDigits = NN_Digits (c, digits);
  207.  
  208.   for (i = 0; i < bDigits; i++)
  209.     t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
  210.   
  211.   NN_Assign (a, t, 2 * digits);
  212.   
  213.   /* Zeroize potentially sensitive information.
  214.    */
  215.   R_memset ((POINTER)t, 0, sizeof (t));
  216. }
  217.  
  218. /* Computes a = b mod c.
  219.  
  220.    Lengths: a[cDigits], b[bDigits], c[cDigits].
  221.    Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
  222.  */
  223. void NN_Mod (a, b, bDigits, c, cDigits)
  224. NN_DIGIT *a, *b, *c;
  225. unsigned int bDigits, cDigits;
  226. {
  227.   NN_DIGIT t[2 * MAX_NN_DIGITS];
  228.   
  229.   NN_Div (t, a, b, bDigits, c, cDigits);
  230.   
  231.   /* Zeroize potentially sensitive information.
  232.    */
  233.   R_memset ((POINTER)t, 0, sizeof (t));
  234. }
  235.  
  236. /* Computes a = b * c mod d.
  237.  
  238.    Lengths: a[digits], b[digits], c[digits], d[digits].
  239.    Assumes d > 0, digits < MAX_NN_DIGITS.
  240.  */
  241. void NN_ModMult (a, b, c, d, digits)
  242. NN_DIGIT *a, *b, *c, *d;
  243. unsigned int digits;
  244. {
  245.   NN_DIGIT t[2*MAX_NN_DIGITS];
  246.  
  247.   NN_Mult (t, b, c, digits);
  248.   NN_Mod (a, t, 2 * digits, d, digits);
  249.   
  250.   /* Zeroize potentially sensitive information.
  251.    */
  252.   R_memset ((POINTER)t, 0, sizeof (t));
  253. }
  254.  
  255.  
  256. /*
  257.  * PGP 2.6's mpilib contains a faster modular exponentiation routine,
  258.  * mp_modexp.  If USEMPILIB is defined, NN_ModExp is replaced in the
  259.  * PGP 2.6 sources with a stub call to mp_modexp.  If USEMPILIB is
  260.  * not defined, we'll get a pure (albeit slower) RSAREF
  261.  * implementation.
  262.  *
  263.  * The RSAREF license, clause 1(c), permits "...modify[ing] the
  264.  * Program in any manner for porting or performance improvement
  265.  * purposes..."
  266.  */
  267. #ifndef USEMPILIB
  268. /* Computes a = b^c mod d.
  269.  
  270.    Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
  271.    Assumes b < d, d > 0, cDigits > 0, dDigits > 0,
  272.            dDigits < MAX_NN_DIGITS.
  273.  */
  274. void NN_ModExp (a, b, c, cDigits, d, dDigits)
  275. NN_DIGIT *a, *b, *c, *d;
  276. unsigned int cDigits, dDigits;
  277. {
  278.   NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
  279.   int i;
  280.   unsigned int ciBits, j, s;
  281.  
  282.   /* Store b, b^2 mod d, and b^3 mod d.
  283.    */
  284.   NN_Assign (bPower[0], b, dDigits);
  285.   NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
  286.   NN_ModMult (bPower[2], bPower[1], b, d, dDigits);
  287.   
  288.   NN_ASSIGN_DIGIT (t, 1, dDigits);
  289.  
  290.   cDigits = NN_Digits (c, cDigits);
  291.   for (i = cDigits - 1; i >= 0; i--) {
  292.     ci = c[i];
  293.     ciBits = NN_DIGIT_BITS;
  294.     
  295.     /* Scan past leading zero bits of most significant digit.
  296.      */
  297.     if (i == (int)(cDigits - 1)) {
  298.       while (! DIGIT_2MSB (ci)) {
  299.         ci <<= 2;
  300.         ciBits -= 2;
  301.       }
  302.     }
  303.  
  304.     for (j = 0; j < ciBits; j += 2, ci <<= 2) {
  305.       /* Compute t = t^4 * b^s mod d, where s = two MSB's of d.
  306.        */
  307.       NN_ModMult (t, t, t, d, dDigits);
  308.       NN_ModMult (t, t, t, d, dDigits);
  309.       if (s = DIGIT_2MSB (ci))
  310.         NN_ModMult (t, t, bPower[s-1], d, dDigits);
  311.     }
  312.   }
  313.   
  314.   NN_Assign (a, t, dDigits);
  315.   
  316.   /* Zeroize potentially sensitive information.
  317.    */
  318.   R_memset ((POINTER)bPower, 0, sizeof (bPower));
  319.   R_memset ((POINTER)t, 0, sizeof (t));
  320. }
  321. #endif
  322.  
  323. /* Compute a = 1/b mod c, assuming inverse exists.
  324.    
  325.    Lengths: a[digits], b[digits], c[digits].
  326.    Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
  327.  */
  328. void NN_ModInv (a, b, c, digits)
  329. NN_DIGIT *a, *b, *c;
  330. unsigned int digits;
  331. {
  332.   NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
  333.     u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
  334.     v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
  335.   int u1Sign;
  336.  
  337.   /* Apply extended Euclidean algorithm, modified to avoid negative
  338.      numbers.
  339.    */
  340.   NN_ASSIGN_DIGIT (u1, 1, digits);
  341.   NN_AssignZero (v1, digits);
  342.   NN_Assign (u3, b, digits);
  343.   NN_Assign (v3, c, digits);
  344.   u1Sign = 1;
  345.  
  346.   while (! NN_Zero (v3, digits)) {
  347.     NN_Div (q, t3, u3, digits, v3, digits);
  348.     NN_Mult (w, q, v1, digits);
  349.     NN_Add (t1, u1, w, digits);
  350.     NN_Assign (u1, v1, digits);
  351.     NN_Assign (v1, t1, digits);
  352.     NN_Assign (u3, v3, digits);
  353.     NN_Assign (v3, t3, digits);
  354.     u1Sign = -u1Sign;
  355.   }
  356.   
  357.   /* Negate result if sign is negative.
  358.     */
  359.   if (u1Sign < 0)
  360.     NN_Sub (a, c, u1, digits);
  361.   else
  362.     NN_Assign (a, u1, digits);
  363.  
  364.   /* Zeroize potentially sensitive information.
  365.    */
  366.   R_memset ((POINTER)q, 0, sizeof (q));
  367.   R_memset ((POINTER)t1, 0, sizeof (t1));
  368.   R_memset ((POINTER)t3, 0, sizeof (t3));
  369.   R_memset ((POINTER)u1, 0, sizeof (u1));
  370.   R_memset ((POINTER)u3, 0, sizeof (u3));
  371.   R_memset ((POINTER)v1, 0, sizeof (v1));
  372.   R_memset ((POINTER)v3, 0, sizeof (v3));
  373.   R_memset ((POINTER)w, 0, sizeof (w));
  374. }
  375.  
  376. /* Computes a = gcd(b, c).
  377.  
  378.    Lengths: a[digits], b[digits], c[digits].
  379.    Assumes b > c, digits < MAX_NN_DIGITS.
  380.  */
  381. void NN_Gcd (a, b, c, digits)
  382. NN_DIGIT *a, *b, *c;
  383. unsigned int digits;
  384. {
  385.   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS];
  386.  
  387.   NN_Assign (u, b, digits);
  388.   NN_Assign (v, c, digits);
  389.  
  390.   while (! NN_Zero (v, digits)) {
  391.     NN_Mod (t, u, digits, v, digits);
  392.     NN_Assign (u, v, digits);
  393.     NN_Assign (v, t, digits);
  394.   }
  395.  
  396.   NN_Assign (a, u, digits);
  397.  
  398.   /* Zeroize potentially sensitive information.
  399.    */
  400.   R_memset ((POINTER)t, 0, sizeof (t));
  401.   R_memset ((POINTER)u, 0, sizeof (u));
  402.   R_memset ((POINTER)v, 0, sizeof (v));
  403. }
  404.  
  405. /* Returns sign of a - b.
  406.  
  407.    Lengths: a[digits], b[digits].
  408.  */
  409. int NN_Cmp (a, b, digits)
  410. NN_DIGIT *a, *b;
  411. unsigned int digits;
  412. {
  413.   int i;
  414.   
  415.   for (i = digits - 1; i >= 0; i--) {
  416.     if (a[i] > b[i])
  417.       return (1);
  418.     if (a[i] < b[i])
  419.       return (-1);
  420.   }
  421.  
  422.   return (0);
  423. }
  424.  
  425. /* Returns nonzero iff a is zero.
  426.  
  427.    Lengths: a[digits].
  428.  */
  429. int NN_Zero (a, digits)
  430. NN_DIGIT *a;
  431. unsigned int digits;
  432. {
  433.   unsigned int i;
  434.   
  435.   for (i = 0; i < digits; i++)
  436.     if (a[i])
  437.       return (0);
  438.     
  439.   return (1);
  440. }
  441.  
  442. /* Returns the significant length of a in bits.
  443.  
  444.    Lengths: a[digits].
  445.  */
  446. unsigned int NN_Bits (a, digits)
  447. NN_DIGIT *a;
  448. unsigned int digits;
  449. {
  450.   if ((digits = NN_Digits (a, digits)) == 0)
  451.     return (0);
  452.  
  453.   return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
  454. }
  455.  
  456. /* Returns the significant length of a in digits.
  457.  
  458.    Lengths: a[digits].
  459.  */
  460. unsigned int NN_Digits (a, digits)
  461. NN_DIGIT *a;
  462. unsigned int digits;
  463. {
  464.   int i;
  465.   
  466.   for (i = digits - 1; i >= 0; i--)
  467.     if (a[i])
  468.       break;
  469.  
  470.   return (i + 1);
  471. }
  472.  
  473. /* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
  474.  
  475.    Lengths: a[digits], b[digits].
  476.    Requires c < NN_DIGIT_BITS.
  477.  */
  478. static NN_DIGIT NN_LShift (a, b, c, digits)
  479. NN_DIGIT *a, *b;
  480. unsigned int c, digits;
  481. {
  482.   NN_DIGIT bi, carry;
  483.   unsigned int i, t;
  484.   
  485.   if (c >= NN_DIGIT_BITS)
  486.     return (0);
  487.   
  488.   t = NN_DIGIT_BITS - c;
  489.  
  490.   carry = 0;
  491.  
  492.   for (i = 0; i < digits; i++) {
  493.     bi = b[i];
  494.     a[i] = (bi << c) | carry;
  495.     carry = c ? (bi >> t) : 0;
  496.   }
  497.   
  498.   return (carry);
  499. }
  500.  
  501. /* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.
  502.  
  503.    Lengths: a[digits], b[digits].
  504.    Requires: c < NN_DIGIT_BITS.
  505.  */
  506. static NN_DIGIT NN_RShift (a, b, c, digits)
  507. NN_DIGIT *a, *b;
  508. unsigned int c, digits;
  509. {
  510.   NN_DIGIT bi, carry;
  511.   int i;
  512.   unsigned int t;
  513.   
  514.   if (c >= NN_DIGIT_BITS)
  515.     return (0);
  516.   
  517.   t = NN_DIGIT_BITS - c;
  518.  
  519.   carry = 0;
  520.  
  521.   for (i = digits - 1; i >= 0; i--) {
  522.     bi = b[i];
  523.     a[i] = (bi >> c) | carry;
  524.     carry = c ? (bi << t) : 0;
  525.   }
  526.   
  527.   return (carry);
  528. }
  529.  
  530. /* Computes a = c div d and b = c mod d.
  531.  
  532.    Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
  533.    Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
  534.            dDigits < MAX_NN_DIGITS.
  535.  */
  536. static void NN_Div (a, b, c, cDigits, d, dDigits)
  537. NN_DIGIT *a, *b, *c, *d;
  538. unsigned int cDigits, dDigits;
  539. {
  540.   NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], t;
  541.   int i;
  542.   unsigned int ddDigits, shift;
  543.   
  544.   ddDigits = NN_Digits (d, dDigits);
  545.   if (ddDigits == 0)
  546.     return;
  547.   
  548.   /* Normalize operands.
  549.    */
  550.   shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
  551.   NN_AssignZero (cc, ddDigits);
  552.   cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
  553.   NN_LShift (dd, d, shift, ddDigits);
  554.   t = dd[ddDigits-1];
  555.   
  556.   NN_AssignZero (a, cDigits);
  557.  
  558.   for (i = cDigits-ddDigits; i >= 0; i--) {
  559.     /* Underestimate quotient digit and subtract.
  560.      */
  561.     if (t == MAX_NN_DIGIT)
  562.       ai = cc[i+dDigits];
  563.     else
  564.       NN_DigitDiv (&ai, &cc[i+ddDigits-1], t + 1);
  565.     cc[i+ddDigits] -= NN_SubDigitMult (&cc[i], &cc[i], ai, dd, ddDigits);
  566.  
  567.     /* Correct estimate.
  568.      */
  569.     while (cc[i+ddDigits] || (NN_Cmp (&cc[i], dd, ddDigits) >= 0)) {
  570.       ai++;
  571.       cc[i+ddDigits] -= NN_Sub (&cc[i], &cc[i], dd, ddDigits);
  572.     }
  573.     
  574.     a[i] = ai;
  575.   }
  576.   
  577.   /* Restore result.
  578.    */
  579.   NN_AssignZero (b, dDigits);
  580.   NN_RShift (b, cc, shift, ddDigits);
  581.  
  582.   /* Zeroize potentially sensitive information.
  583.    */
  584.   R_memset ((POINTER)cc, 0, sizeof (cc));
  585.   R_memset ((POINTER)dd, 0, sizeof (dd));
  586. }
  587.  
  588. /* Computes a = b + c*d, where c is a digit. Returns carry.
  589.  
  590.    Lengths: a[digits], b[digits], d[digits].
  591.  */
  592. static NN_DIGIT NN_AddDigitMult (a, b, c, d, digits)
  593. NN_DIGIT *a, *b, c, *d;
  594. unsigned int digits;
  595. {
  596.   NN_DIGIT carry, t[2];
  597.   unsigned int i;
  598.  
  599.   if (c == 0)
  600.     return (0);
  601.  
  602.   carry = 0;
  603.   for (i = 0; i < digits; i++) {
  604.     NN_DigitMult (t, c, d[i]);
  605.     if ((a[i] = b[i] + carry) < carry)
  606.       carry = 1;
  607.     else
  608.       carry = 0;
  609.     if ((a[i] += t[0]) < t[0])
  610.       carry++;
  611.     carry += t[1];
  612.   }
  613.   
  614.   return (carry);
  615. }
  616.  
  617. /* Computes a = b - c*d, where c is a digit. Returns borrow.
  618.  
  619.    Lengths: a[digits], b[digits], d[digits].
  620.  */
  621. static NN_DIGIT NN_SubDigitMult (a, b, c, d, digits)
  622. NN_DIGIT *a, *b, c, *d;
  623. unsigned int digits;
  624. {
  625.   NN_DIGIT borrow, t[2];
  626.   unsigned int i;
  627.  
  628.   if (c == 0)
  629.     return (0);
  630.  
  631.   borrow = 0;
  632.   for (i = 0; i < digits; i++) {
  633.     NN_DigitMult (t, c, d[i]);
  634.     if ((a[i] = b[i] - borrow) > (MAX_NN_DIGIT - borrow))
  635.       borrow = 1;
  636.     else
  637.       borrow = 0;
  638.     if ((a[i] -= t[0]) > (MAX_NN_DIGIT - t[0]))
  639.       borrow++;
  640.     borrow += t[1];
  641.   }
  642.   
  643.   return (borrow);
  644. }
  645.  
  646. /* Returns the significant length of a in bits, where a is a digit.
  647.  */
  648. static unsigned int NN_DigitBits (a)
  649. NN_DIGIT a;
  650. {
  651.   unsigned int i;
  652.   
  653.   for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
  654.     if (a == 0)
  655.       break;
  656.     
  657.   return (i);
  658. }
  659.